// 循序栈
#include <iostream>

// 自定义allocator
template <typename T>
struct MyAllocator
{
    T* allocate(size_t size)
    {
        // 开辟一块堆空间
        return (T*) malloc(sizeof(T) * size);
    }
    void deAllocate(T* p)
    {
        // 释放整块内存
        free(p);
    }
    void construct(T* p, const T& val)
    {
        // 在P位置新建一个val对象调用拷贝构造函数
        new (p) T(val);
    }
    void destory(T* p)
    {
        // 对象进行析构
        p->~T();
    }
};

template <typename T, typename Alloc = MyAllocator<T>>
class MySeqStack
{
public:
    // 构造函数
    MySeqStack(int size = 10)
        :_last(0)
        ,_size(size)
    {
        // 开辟一块堆空间
        _p_stack = _allocator.allocate(size);
    }
    ~MySeqStack()
    {
        // 将容器中的有效对象析构
        for(int i = 0; i < _last; i ++)
        {
            _allocator.destory(_p_stack + i);
        }
        // 释放整个容器内存
        _allocator.deAllocate(_p_stack);
        _p_stack = nullptr;
    }
    // 拷贝构造函数
    MySeqStack(const MySeqStack<T>& src)
    {
        // 开辟一块内存
        _p_stack = _allocator.allocate(src._size);
        // 将源内存中的数据赋值到目标内存中
        for(int i = 0; i < src._last; i ++)
        {
            _allocator.construct(_p_stack + i, src._p_stack[i]);
        }
    }
    // 赋值运算符重载
    MySeqStack<T>& operator=(const MySeqStack<T>& src)
    {
        // 判断是否是自赋值
        if(this == &src)
            return *this;
        // 删除空间中的有效对象
        for(int i = 0; i < _last; i ++)
        {
            _allocator.destory(_p_stack + i);
        }
        // 清除整个堆空间
        _allocator.deAllocate(_p_stack);
        _p_stack = _allocator.allocate(src._size);
        for(int i = 0; i < src._last; i ++)
        {
            _allocator.construct(_p_stack + i, src._p_stack[i]);
        }
        _last = src._last;
        _size = src._size;
        return *this;
    }
    void push_back(const T& val)
    {
        if(full())
            expand();
        _allocator.construct(_p_stack + _last, val);
        _last ++;
    }
    void pop_back()
    {
        if(empty())
            return;
        _allocator.destory(_p_stack + (--_last));
    }
    T top() const
    {
        return _p_stack[_last - 1];
    }
    bool full() const
    {
        return _last == _size;
    }
    bool empty() const
    {
        return _last == 0;
    }
    int size() const
    {
        return _size;
    }
    int length() const
    {
        return _last;
    }
private:
    T* _p_stack;
    int _last;
    int _size;
    Alloc _allocator;
    void expand()
    {
        // 临时生成一个空间
        T* ptmp = _allocator.allocate(_size * 2);
        for(int i = 0; i < _last; i ++)
        {
            _allocator.construct(ptmp + i, _p_stack[i]);
            _allocator.destory(_p_stack + i);
        }
        _allocator.deAllocate(_p_stack);
        _p_stack = ptmp;

        _size *= 2;
    }
};


int main(int argc, char const *argv[])
{
    MySeqStack<int> seq;
    for(int i = 0; i < 10; i ++)
    {
        seq.push_back(i);
    }
    while(!seq.empty())
    {
        std::cout << seq.top() << std::endl;
        seq.pop_back();
    }
    std::cout << "-----------------" << std::endl;
    return 0;
}
